package _18_剑指OfferII;

import java.util.HashSet;
import java.util.Set;

public class _093_剑指OfferII最长斐波那契数列 {

    public static void main(String[] args) {

        _093_剑指OfferII最长斐波那契数列 v = new _093_剑指OfferII最长斐波那契数列();

        int[] ins = {1, 2, 3, 4, 5, 6, 7, 8};
        System.out.println(v.lenLongestFibSubseq(ins));
    }

    // 动态规划解法, 有序数组的三数之和
    // 可以用三指针来求解
    public int lenLongestFibSubseq(int[] arr) {
        int len = arr.length;
        int[][] dp = new int[len][len];
        // 固定三指针位置
        int ans = 0;
        for (int i = 0; i < len; i++) {
            int left = 0;
            int right = i - 1;
            while (left < right) {
                int sum = arr[left] + arr[right];
                if (sum == arr[i]) {
                    dp[right][i] = Math.max(dp[right][i], dp[left][right] + 1);
                    ans = Math.max(ans, dp[right][i]);
                    left++;
                    right--;
                } else if (sum > arr[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ans == 0? 0: ans + 2;
    }

    // 暴力解法
    public int lenLongestFibSubseq1(int[] arr) {
        Set<Integer> sets = new HashSet<>();
        for (int i : arr) sets.add(i);
        int len = arr.length;
        int ans = 0;
        for (int i = 0; i < len; ++i) {
            for (int j = i + 1; j < len; ++j) {
                int next = arr[i] + arr[j];
                int prev = arr[j];
                int length = 2;
                while (sets.contains(next)) {
                    int temp = next;
                    next = prev + next;
                    prev = temp;
                    ans = Math.max(ans, ++length);
                }
            }
        }
        return ans;
    }

}
